package com.gozap.sort.tree;

public class TreeOperation {

	static int[] arr = new int[] { 9, 4, 12, 10, 6, 29, 34, 98, 82, 14, 15 };

	/**
	 * 创建树
	 * 
	 * @return
	 */
	public Tree buildTree() {

		Tree tree = new Tree(arr[0]);
		int len = arr.length;
		if (len > 1) {
			for (int i = 1; i < len; i++) {
				insert(tree, arr[i]);
			}
		}

		return tree;
	}

	/**
	 * 将一个值插入到数中
	 * 
	 * @param tree
	 * @param key
	 */
	public void insert(Tree tree, int key) {
		if (null != tree) {
			Tree c = tree;
			Tree p = null;
			boolean isLeft = true;
			while (c != null) {
				if (key < ((Integer) (c.getKey()))) {
					p = c;
					c = p.getLeft();
					isLeft = true;
				} else {
					p = c;
					c = p.getRight();
					isLeft = false;
				}
			}

			Tree t = new Tree(key);
			t.setParent(p);
			if (isLeft) {
				p.setLeft(t);
			} else {
				p.setRight(t);
			}
		}
	}

	/**
	 * 查找，存在则返回，失败返回null
	 * 
	 * @param key
	 * @return
	 */
	public Tree search(Tree tree, int key) {

		if (tree != null) {
			Tree t = tree;
			while (t != null) {
				if (key == ((Integer) t.getKey())) {
					return t;
				} else if (key < ((Integer) t.getKey())) {
					t = t.getLeft();
				} else {
					t = t.getRight();
				}
			}
		}
		return null;
	}

	/**
	 * 中序遍历
	 */
	public void middleTraverse(Tree tree) {
		Tree left = tree.getLeft();
		Tree right = tree.getRight();

		if (left != null) {
			middleTraverse(left);
		}

		System.out.print(tree.getKey() + " ");

		if (right != null) {
			middleTraverse(right);
		}

	}

	/**
	 * 最大的节点
	 * 
	 * @param tree
	 * @return
	 */
	public Tree max(Tree tree) {
		if (tree != null) {
			Tree t = tree;
			while (t.getRight() != null) {
				t = t.getRight();
			}
			return t;
		}
		return null;
	}

	/**
	 * 最小的节点
	 * 
	 * @param tree
	 * @return
	 */
	public Tree min(Tree tree) {
		if (tree != null) {
			Tree t = tree;
			while (t.getLeft() != null) {
				t = t.getLeft();
			}
			return t;
		}
		return null;
	}

	/**
	 * 中序遍历某个节点前驱
	 * 
	 * @param tree
	 * @param key
	 * @return
	 */
	public Tree before(Tree tree) {
		if (tree != null) {
			Tree t;
			Tree left = tree.getLeft();
			if (left != null) {
				t = max(left);
				return t;
			}

			t = tree;
			Tree p = t.getParent();
			if (p == null) {
				return null;
			}

			while (p != null && p.getRight() != t) {
				t = p;
				p = t.getParent();
			}
			if (p == null) {
				return null;
			} else {
				return p;
			}
		}
		return null;
	}

	/**
	 * 中序遍历某个节点后继
	 * 
	 * @param tree
	 * @param key
	 * @return
	 */
	public Tree after(Tree tree) {
		if (tree != null) {

			Tree right = tree.getRight();
			Tree t;
			if (right != null) {
				t = min(right);
				return t;
			}

			t = tree;
			Tree p = t.getParent();
			if (p == null) {
				return null;
			}

			while (p != null && p.getLeft() != t) {
				t = p;
				p = t.getParent();
			}
			if (p == null) {
				return null;
			} else {
				return p;
			}

		}

		return null;
	}

	/**
	 * 从树中删除一个节点,返回父节点
	 * 
	 * @param key
	 */
	public Tree remove(Tree tree) {
		if (null != tree) {
			Tree p = tree.getParent();
			Tree left = tree.getLeft();
			Tree right = tree.getRight();
			int childLen = (left == null ? 0 : 1) + (right == null ? 0 : 1);

			if (childLen == 0) {
				p.setLeft(null);
				p.setRight(null);
				tree = null;
				return p;
			} else if (childLen == 1) {
				boolean isLeft = true;

				if (tree != p.getLeft()) {
					isLeft = false;
				}
				Tree child;
				if (left == null) {
					child = right;
				} else {
					child = left;
				}
				if (isLeft) {
					p.setLeft(child);
				} else {
					p.setRight(child);
				}
				child = null;
				return p;
			} else {
				Tree after=after(tree);
				int t=(Integer)tree.getKey();
				tree.setKey(after.getKey());
				after.setKey(t);
				return remove(after);
			}
		}
		return null;
	}
}
